package com.zzg.datastructure.stack;

import java.util.*;

/**
 * @Author zhengzg
 * @Date 2022-08-18
 * @Version v1.0
 */
public class PolandNotation {
    public static void main(String[] args) {

        // 将中缀表达式转化为后缀表达式
        // 定义一个中缀表达式
        String expression = "1+((2+3)*4)-5";
        List<String> infixExpressionList = toInfixExpressionList(expression);
        // 将得到的中缀表达式集合转化为后缀表达式集合
        List<String> suffixExpressionList = parseSuffixExpressionList(infixExpressionList);

        // 先定义逆波兰表达式
        // (3+6) * 5 - 8 / 6=> 3 6 + 5 * 8 6 / -
//        String suffixExpression = "3 6 + 5 * 8 6 / -";
//        // 将表达式转化为数组
//        List<String> list = Arrays.asList(suffixExpression.split(" "));
//        // 计算结果
        int res = calculate(suffixExpressionList);
        System.out.println("逆波兰表达式结果为：" + res);
    }

    /**
     * 中缀表达式集合转后缀表达式集合
     * @param infixExpressionList 中缀表达式集合
     * @return 后缀表达式集合
     */
    private static List<String> parseSuffixExpressionList(List<String> infixExpressionList) {
        // 定义栈，符号栈
        Stack<String> operStack = new Stack<>();

        // 定义集合，存放后缀表达式
        ArrayList<String> s2 = new ArrayList<>();
        infixExpressionList.forEach(item -> {
            // 如果是数字，直接加入s2
            if (item.matches("\\d+")){
                s2.add(item);
            } else if (Objects.equals("(",item)){
                operStack.push(item);
            } else if (Objects.equals(")",item)){
                // 如果是右括号，则依次弹出operStack栈顶的运算符，知道遇到左括号为止，此时，将丢弃一对括号
                while (!Objects.equals(operStack.peek(),"(")){
                    s2.add(operStack.pop());
                }
                // 遇到左括号 弹栈
                operStack.pop();
            } else {
                // 当item优先级小于等于operStack中的优先级时，弹栈加入s2，在继续进行判断
                while (operStack.size() != 0 && Operation.getRank(operStack.peek()) >= Operation.getRank(item)){
                    s2.add(operStack.pop());
                }

                // 将item压入栈
                operStack.push(item);
            }
        });

        // 将operStack中剩余的运算符依次弹出，加入s2
        while (operStack.size() != 0){
            s2.add(operStack.pop());
        }

        return s2;
    }

    /**
     * 中缀表达式 转 中缀表达式集合
     * @param expression 中缀表达式
     * @return 中缀表达式集合
     */
    private static List<String> toInfixExpressionList(String expression) {
        // 定义一个list存放中缀表达式
        ArrayList<String> ls = new ArrayList<>();
        // 指针，遍历表达式字符串
        int helper = 0;
        // 对多位数的拼接
        StringBuilder express = new StringBuilder();
        // 每遍历一个字符就放入c
        char c;
        do {
            // 如果c是一个非0数字，我们加入ls
            if ((c = expression.charAt(helper)) < 48 || (c = expression.charAt(helper)) > 57){
                ls.add(String.valueOf(c));
                // 指针后移
                helper++;
            } else {
                // 是数字，需要考虑多位数
                express.delete(0,expression.length());
                while (helper < expression.length() && (c=expression.charAt(helper)) >= 48 && (c = expression.charAt(helper)) <= 57){
                    express.append(c);
                    helper++;
                }
                ls.add(express.toString());
            }
        }while (helper < expression.length());

        return ls;
    }

    /**
     * 完成对逆波兰表达式的运算
     * @param list 表达式集合
     * @return 计算结果
     *
     * 计算思路：
     * 1）从左到右扫描，将30和6压入栈
     * 2）遇到+运算符，因此弹出30和6（30为栈顶元素，6为次顶元素），计算30+6的值，将结果入栈
     * 3）将5入栈
     * 4）扫描到 *，将36，与 5弹出进行乘法运算，结果入栈
     * 5）扫描到 6入栈
     * 6）扫描到 -,将栈顶元素与次顶元素弹栈，计算结果，入栈
     */
    private static int calculate(List<String> list) {
        Stack<String> stack = new Stack<>();

        // 遍历表达式集合
        for (String item : list){
            // 匹配数字
            if (item.matches("\\d+")) {
                // 入栈
                stack.push(item);
            } else {
                // 字符，弹栈计算
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                // 存储计算结果
                int res = 0;
                switch (item) {
                    case "*":
                        res = num1 * num2;
                        break;
                    case "/":
                        res = num1 / num2;
                        break;
                    case "-":
                        res = num1 - num2;
                        break;
                    case "+":
                        res = num1 + num2;
                        break;
                    default:
                        throw new RuntimeException("表达式数据错误");
                }
                // 结果入栈
                stack.push(String.valueOf(res));
            }
        }
        return Integer.parseInt(stack.pop());
    }
}
